package problem.year2021.january;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
 * <p>
 * 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
 * <p>
 * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class January19 {
    public int minCostConnectPoints(int[][] points) {
        if (points.length == 1) return 0;
        if (points.length == 2) return len(points[0], points[1]);
        // 设置一个集合，用来记录最小费用点
        List<int[]> list1 = new ArrayList<>(Arrays.asList(points));
        List<int[]> list2 = new ArrayList<>();
        list2.add(list1.get(0));
        list1.remove(0);
        int sum = 0;
        while (list1.size() > 0) {
            int length = -1; // 记录距离
            int index = -1; // 记录索引值
            for (int i = 0; i < list2.size(); i++) {
                for (int j = 0; j < list1.size(); j++) {
                    if (length == -1) {
                        length = len(list2.get(i), list1.get(j));
                        index = j;
                        continue;
                    }
                    if (length > len(list1.get(j), list2.get(i))) {
                        index = j;
                        length = len(list1.get(j), list2.get(i));
                    }
                }
            }
            sum += length;
            list2.add(list1.get(index));
            list1.remove(index);
        }
        return sum;
    }

    private static int len(int[] a, int[] b) {
        return Math.abs(a[1] - b[1]) + Math.abs(a[0] - b[0]);
    }

    public static void main(String[] args) {
        // [[0,0],[2,2],[3,10],[5,2],[7,0]] 20
        // [[3,12],[-2,5],[-4,1]] 18
        //  [[0,0],[1,1],[1,0],[-1,1]] 4
        // [[-1000000,-1000000],[1000000,1000000]] 4000000
        // [[0,0]] 0
//        int[][] ints = new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
//        int[][] ints = new int[][]{{3, 12}, {-2, 5}, {-4, 1}};
//        int[][] ints = new int[][]{{0, 0}, {1, 1}, {1, 0}, {-1, 1}};
//        int[][] ints = new int[][]{{-1000000, -1000000}, {1000000, 1000000}};
        int[][] ints = new int[][]{{0, 0}};
        System.out.println(new January19().minCostConnectPoints(ints));
    }
}
